#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<queue>
using namespace std;
typedef struct BiTnode{
    struct BiTnode *lchild,*rchild;
    int data;
}BiTnode,*BiTree;
BiTree newNode(int data){
    BiTree node=(BiTree)malloc(sizeof(struct BiTnode));
    node->data=data;
    node->lchild=NULL;
    node->rchild=NULL;
    return node;
}
BiTree create_bst(BiTree node,int data){
    if(!node)
        return newNode(data);
    if(node->data<data)
        node->rchild=create_bst(node->rchild,data);
    else
        node->lchild=create_bst(node->lchild,data);
    return node;
}
void PreOrder_Iterative(BiTree root){
    if(root==NULL)
        return;
    stack<BiTree> nodeStack;
    nodeStack.push(root);
    while(!nodeStack.empty()){
        BiTree node=nodeStack.top();
        printf("%d ",node->data);
        nodeStack.pop();
        if(node->rchild)    nodeStack.push(node->rchild);
        if(node->lchild)    nodeStack.push(node->lchild);
        
    }
}
void inOrder_Iterative(BiTree root){
    if(NULL==root)
        return;
    stack<BiTree> nodeStack;
    BiTree curNode=root;
    while(curNode||!nodeStack.empty()){
        while (curNode)
        {
            nodeStack.push(curNode);
            curNode=curNode->lchild;
        }
        curNode=nodeStack.top();
        printf("%d ",curNode->data);
        nodeStack.pop();
        curNode=curNode->rchild;
    }
}
void postOrder_Iterative(BiTree root){
    if(NULL==root)
        return;
    stack<BiTree> nodeStack;
    stack<BiTree> resStack;
    nodeStack.push(root);
    while(!nodeStack.empty()){
        BiTree node=nodeStack.top();
        resStack.push(node);
        nodeStack.pop();
        if(node->lchild)    nodeStack.push(node->lchild);
        if(node->rchild)    nodeStack.push(node->rchild);
    }
    while(!resStack.empty()){
        printf("%d ",resStack.top()->data);
        resStack.pop();
    }
}
bool path(BiTree root, BiTree node, stack<BiTree> &s)
{
    BiTree p = root, pre=NULL;
    if (p == NULL || node == NULL || !s.empty())
        return false;
    while (p!=NULL || !s.empty()) {
        while (p) {//先往左边找，找到了就退出
            s.push(p);
            if (p == node)
                return true;
            p = p->lchild;
        }
        if (!s.empty()) {//栈顶元素左子树为null且未找到，往右子树找
            p=s.top();//栈顶元素右子树为null，或者右子树被遍历过，则弹栈
            while(p->rchild==NULL ||pre!=NULL && p->rchild==pre){
                pre=s.top();
                s.pop();
                p=s.top();
            }//继续遍历右子树
            p=p->rchild;
        } 
    }
    return false;
}
void level_traverse(BiTree root,stack<BiTree> &s){
    if(root==NULL)
        return;
    queue<BiTree> q;
    BiTree p=root;
    q.push(p);
    while(!q.empty()){
        p=q.front();
        s.push(p);
        q.pop();
        if(p->lchild!=NULL) q.push(p->lchild);
        if(p->rchild!=NULL) q.push(p->rchild);
    }
}
int main(){
    BiTree root=NULL;
    int arr[7]={10,20,5,24,7,8,6};
    for(int i=0;i<7;i++){
        root=create_bst(root,arr[i]);
    }
    /*
        10
       /  \
      5    20
       \      \
        7      24
       / \
      6   8
    */
    printf("\n-----------非递归先序遍历---------------\n");
    PreOrder_Iterative(root);
    printf("\n-----------非递归中序遍历---------------\n");
    inOrder_Iterative(root);
    printf("\n-----------非递归后序遍历---------------\n");
    postOrder_Iterative(root);
    stack<BiTree> s;
    path(root,root->lchild->rchild->lchild,s);
    printf("\n------栈元素--------\n");
    while(!s.empty()){
        printf("%d ",s.top()->data);
        s.pop();
    }
    printf("\n------反向层次遍历--------\n");
    stack<BiTree> ss;
    level_traverse(root,ss);
     while(!ss.empty()){
        printf("%d ",ss.top()->data);
        ss.pop();
    }
    return 0;
}